package com.interview.javabasic.DataStructrue.ThreadBinaryTree;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

public class ThreadedBinarTreeDemo {
    public static void main(String[] args) {
        //测试中序遍历线索二叉树
        TreeNode root = new TreeNode(1, "tom");
        TreeNode node1 = new TreeNode(3, "jack");
        TreeNode node2 = new TreeNode(6, "smith");
        TreeNode node3 = new TreeNode(8, "mary");
        TreeNode node4 = new TreeNode(10, "king");
        TreeNode node5 = new TreeNode(14, "dim");

        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node1.setRight(node4);
        node2.setLeft(node5);

        ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree();
        threadBinaryTree.setRoot(root);
        threadBinaryTree.threadedNodes(root);

        //测试：
        TreeNode left = node4.getLeft();
        System.out.println("10节点的前驱节点"+left);
    }
}

class TreeNode{
    private int no;
    private String name;
    private TreeNode left;
    private TreeNode right;
    //如果leftType ==0 表示指向的是左子树，如果1则表示指向前驱节点
    //如果rightType == 0 表示指向的是右子树，如果1表示指向后继节点
    private int leftType;
    private int rightType;
    public TreeNode(int no,String name){
        this.no = no;
        this.name = name;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }
}

class ThreadBinaryTree{
    private TreeNode root;

    //为了实现线索化，需要创建给指向当前节点的前驱节点的指针
//在进行递归的时候总是保留当前节点的前驱节点
    private TreeNode pre = null;
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //重载
    public void threadedNodes(){
        this.threadedNodes(root);
    }

    //编写对二叉树进行中序线索化的方法
    public void threadedNodes(TreeNode node){
        //如果当前节点为空，
        if (node == null){
            return;
        }
        //(1)先线索化左子树
        threadedNodes(node.getLeft());
        //（2）线索化当前节点
        if (node.getLeft()==null){
            node.setLeft(pre);
            //修改当前指针的类型为，指向的是前驱节点
            node.setLeftType(1);
        }
        //处理后继节点
        if (pre.getRight()==null && pre!=null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;//每次数理之后都让当前节点是下一个节点的前驱节点
        //（3）线索化右子树
        threadedNodes(node.getRight());
    }


}